
/**
 * 二叉树的五种基本形态
 *  1:空二叉树
 *  2:根和空的左右子树
 *  3:根和左子树
 *  4:根和右子树
 *  5:根和左右子树
 */
//创建节点
/**
 * 
 * @param {*} data  当前节点的值
 * @param {*} left 左节点
 * @param {*} right 右节点
 */
function Node (data, left, right) {
    this.data = data
    this.left = left
    this.right = right
}
//展示节点
Node.prototype.show = function () {
    console.log(this.data)
}
//创建二叉树
/**
 *  root 根节点
 */
function Tree () {
    this.root = null
}
//树的插入
Tree.prototype = {
    insert: function (data) {
        var node = new Node(data, null, null);
        if (!this.root) {
            this.root = node;
            return;
        }
        var current = this.root;
        var parent = null;
        while (current) {
            parent = current;
            if (data < parent.data) {
                current = current.left;
                if (!current) {
                    parent.left = node;
                    return;    
                }
            } else {
                current = current.right;
                if (!current) {
                    parent.right = node;
                    return;
                }
            }

        }
    },
    //二叉树前序遍历;首先访问根节点，然后遍历左子树，最后遍历右子树
    preOrder: function (node) {
        if (node) {
            this.preOrder(node.left)
            this.preOrder(node.right)
        }
    },
    //二叉树的中序遍历:首先方问左子树,然后根节点 ,最后右子树
    middleOrder: function (node) {
        if (node) {
            this.middleOrder(node.left)
            node.show()
            this.middleOrder(node.right)
        }
    },
    //二叉树的后序遍历:首先访问左子树 然后右子树 最后根节点
    laterOrder: function (node) {
        if (node) {
            this.laterOrder(node.left)
            this.laterOrder(node.right)
            node.show()
        }
    },
    //获取二叉树中的最小值
    getMin: function () {
        var current = this.root
        while (current) {
            if (!current.left) {
                return current
            }
            current = current.left
        }
    },
    //获取二叉树中的最大值
    getMax: function () {
        var current = this.root
        while (current) {
            if (!current.right) {
                return current
            }
            current = current.right
        }
    },
    getDeep: function () {
        deep = deep || 0
        if (node == null) {
            return deep
        }
        deep++
        var dleft = this.getDeep(node.left, deep)
        var dright = this.getDeep(node.right, deep)
        return Math.max(dleft, dright)
    }
}
var t = new Tree();
// t.insert(3);
// t.insert(8);
// t.insert(1);
// t.insert(2);
// t.insert(5);
// t.insert(7);
// t.insert(6);
// t.insert(0);

t.insert(1);
t.insert(null);
t.insert(2);
t.insert(3);
console.log(t);
// t.middleOrder(t.root);
// console.log(t.getMin(), t.getMax());
// console.log(t.getDeep(t.root, 0));
// console.log(t.getNode(5, t.root));